//
//  BinaryTree.hpp
//  labuladong
//
//  Created by 刘振舟 on 2023/5/23.
//

#ifndef BinaryTree_hpp
#define BinaryTree_hpp

#include <cmath>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <list>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};

class BinaryTreeSolution {
public:
    int maxDepth(TreeNode* root);
    
    int diameterOfBinaryTree(TreeNode* root);
    
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return root;
        }
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
    
    
    Node* connect(Node* root) {
        if (!root) {
            return root;
        }
        deque<Node *> queue;
        queue.push_back(root);
        while (!queue.empty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                Node *top = queue.front();
                queue.pop_front();
                if (i < size - 1) {
                    top->next = queue.front();
                }
                if (top->left) {
                    queue.push_back(top->left);
                }
                if (top->right) {
                    queue.push_back(top->right);
                }
            }
        }
        
        return root;
    }
    
    
    void flatten(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        vector<TreeNode*> list;
        traverseForFlatten(root, list);
        for (int i = 0; i < list.size() - 1; ++i) {
            list[i]->left = nullptr;
            list[i]->right = list[i + 1];
        }
    }
    
    void traverseForFlatten(TreeNode* root, vector<TreeNode*> &list) {
        if (root == nullptr) {
            return;
        }
        list.push_back(root);
        traverseForFlatten(root->left, list);
        traverseForFlatten(root->right, list);
    }
    
    TreeNode* construct(vector<int>& nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        int maxIndex = left;
        for (int i = left + 1; i <= right; ++i) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        TreeNode* root = new TreeNode(nums[maxIndex]);
        root->left = construct(nums, left, maxIndex - 1);
        root->right = construct(nums, maxIndex + 1, right);
        return root;
    }
    
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return construct(nums, 0, nums.size() - 1);
    }
    
    TreeNode* buildTreeByPreAndIn(vector<int>& preorder, vector<int>& inorder) {
        int size = preorder.size();
        int inorderIndex = 0;
        stack<TreeNode*> stk;
        TreeNode* root = new TreeNode(preorder[0]);
        stk.push(root);
        for (int i = 1; i < size; ++i) {
            int preorderVal = preorder[i];
            TreeNode* node = stk.top();
            if (inorder[inorderIndex] != node->val) {
                node->left = new TreeNode(preorderVal);
                stk.push(node->left);
            } else {
                while (!stk.empty() && stk.top()->val == inorder[inorderIndex]) {
                    node = stk.top();
                    stk.pop();
                    ++inorderIndex;
                }
                node->right = new TreeNode(preorderVal);
                stk.push(node->right);
            }
        }
        return root;
    }
    
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int size = inorder.size();
        int inorderIndex = size - 1;
        stack<TreeNode*> stk;
        auto root = new TreeNode(postorder[size - 1]);
        stk.push(root);
        
        for (int i = size - 2; i >= 0; --i) {
            int postorderVal = postorder[i];
            TreeNode* node = stk.top();
            if (inorder[inorderIndex] != node->val) {
                node->right = new TreeNode(postorderVal);
                stk.push(node->right);
            } else {
                while (!stk.empty() && stk.top()->val == inorder[inorderIndex]) {
                    node = stk.top();
                    stk.pop();
                    --inorderIndex;
                }
                node->left = new TreeNode(postorderVal);
                stk.push(node->left);
            }
        }
        return root;
    }
    
    
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        int size = preorder.size();
        unordered_map<int, int> map;
        for (int i = 0; i < size; ++i) {
            map[postorder[i]] = i;
        }
        function<TreeNode* (int, int, int, int)> dfs = [&](int preLeft, int preRight, int postLeft, int postRight) -> TreeNode* {
            if (preLeft > preRight) {
                return nullptr;
            }
//            The preorder[preLeft + 1] is default preorder[preLeft] 's left child;
            int leftCount = 0;
            if (preLeft < preRight)
                leftCount = map[preorder[preLeft + 1]] - postLeft + 1;
//            The left child in posttraversal is postRight - 1
            return new TreeNode(preorder[preLeft],
            dfs(preLeft + 1, preLeft + leftCount, postLeft, postLeft + leftCount - 1),
            dfs(preLeft + leftCount + 1, preRight, postLeft + leftCount, postRight - 1));
        };
        return dfs(0, size - 1, 0, size - 1);
    }

    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        function<int (TreeNode*)> dfs = [&](TreeNode* node) {
            if (!node) {
                return 0;
            }
            auto tri = tuple(node->val, dfs(node->left), dfs(node->right));
//            如果 tri 在 seen 中找到了对应的键，find 函数会返回一个指向该键-值对的迭代器。
//            如果 tri 在 seen 中没有找到对应的键，find 函数会返回 unordered_map::end，这是一个指向 unordered_map 结尾的迭代器。
            if (auto it = seen.find(tri); it != seen.end()) {
                repeat.insert(it->second.first);
                return it->second.second;
            } else {
                seen[tri] = {node, ++idx};
                return idx;
            }
        };
        dfs(root);
        return {repeat.begin(), repeat.end()};
    }
    
private:
//    tri_hash 是一个自定义的哈希函数，用于计算三元组的哈希值。它通过将三个整数的哈希值组合起来生成一个新的哈希值。
//    constexpr 是 C++11 引入的关键字，用于声明一个变量或函数是在编译时就可以计算得到结果的常量表达式。使用 constexpr 可以使编译器在编译时进行常量表达式的计算，从而提高程序的运行效率。
    static constexpr auto tri_hash = [fn = hash<int>()](const tuple<int, int, int>& o) -> size_t {
//        && 是一个引用限定符，它用于声明一个右值引用。
//        [x, y, z] 定义了三个变量，x, y, z，它们会被分别赋值为元组 o 的三个元素。
        auto&& [x, y, z] = o;
        return (fn(x) << 24) ^ (fn(y) << 8) ^ fn(z);
    };
//    decltype(tri_hash)是key（tuple<int, int, int>）的hash计算函数
//    seen{0, tri_hash}：这是一个 unordered_map 的初始化语句。它初始化了 unordered_map，设置了一个默认值 0 和一个自定义的哈希函数 tri_hash。
    unordered_map<tuple<int, int, int>, pair<TreeNode*, int>, decltype(tri_hash)> seen{0, tri_hash};
    unordered_set<TreeNode*> repeat;
    int idx = 0;
};



class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string str;
        function<void (TreeNode*)> rserialize = [&](TreeNode* node) -> void {
            if (node == nullptr) {
                str += "None,";
            } else {
                str += to_string(node->val) + ",";
                rserialize(node->left);
                rserialize(node->right);
            }
        };
        rserialize(root);
        return str;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        list<string> dataArray;
        string item;
        for (char ch : data) {
            if (ch == ',') {
                dataArray.push_back(item);
                item.clear();
            }
            else
                item.push_back(ch);
        }
        if (!item.empty()) {
            dataArray.push_back(item);
        }
        function<TreeNode* ()> rdeserialize = [&]() -> TreeNode* {
            if (dataArray.front() == "None") {
                dataArray.erase(dataArray.begin());
                return nullptr;
            }
            TreeNode* root = new TreeNode(stoi(dataArray.front()));
            dataArray.erase(dataArray.begin());
            root->left = rdeserialize();
            root->right = rdeserialize();
            return root;
        };
        return rdeserialize();
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

#endif /* BinaryTree_hpp */
